Chess Challenges

Computer programs that play chess, solve chess puzzles, or create chess problems are widespread. There is even an annual contest pitting chess playing programs against each other and against human experts. This case study addresses a simple problem related to chess.

Background

The game of chess is played on an 8-by-8 board. The most powerful chess piece is the queen. From a given position, a queen may move anywhere along the same row, column, or diagonal, provided only that it doesn't jump over pieces. The shaded squares in the figure below illustrate the possible queen moves.

Two queens are said to attack each other if either can move to the position of the other - if they are in the same row, column, or diagonal, and no pieces lie between. The figure below shows examples of attacking and non attacking queens.

A puzzle problem dating from the 1700s is to place as many non attacking queens on the chessboard as possible. In this case study, we will design part of the solution to this problem: code to check if any of a set of queens attack one another.

Problem Statement

Design a type to represent a chessboard on which each square either is empty or contains a queen. Also design and test functions with the following headers and descriptions.

def ReadBoard(board):

ReadBoard asks the user to indicate which positions on the board contain queens. (ReadBoard may do this in any manner and need not check for invalid input.)

def PrintBoard(board):

PrintBoard prints the contents of the board as eight lines of eight characters each; the character 'Q' represents a square on the board that contains a queen, and the character '.' represents an empty board square.

def Safe(board):

Safe returns true exactly when the board contains a "safe" position, one in which no two queens on the board attack each other. Two queens attack each other exactly when they lie in the same row, column, or diagonal, and no pieces lie between them on the diagonal.

Each subprogram, except for its use of BoardType, should be independent of the remainder of the program.

Analysis

9.1 How many possibilities are there for two queens on the board to attack each other?

Analysis

9.2 How many diagonals are there on a chess board?

Application

9.3 How many queens can be placed on the chessboard so that none of them attacks one another?

Preparation

The reader should be familiar with dictionary and arrays of dictionary. The solutions in this case study also introduce the manipulation of two-dimensional arrays.

Understanding the Problem and Selecting an Implementation

How does this problem resemble problems in earlier case studies?

For this problem, we are to design a type along with three functions that use the type. This resembles the problem of Space Text, in which we were to design and test a single function that could be used in a variety of programs. As in the Space Text program, the Chess Challenges functions we write must be independent of the program that contains them to allow easy incorporation of the code into other chess programs.

Chess Challenges also resembles the first part of our solution to You Are What You Eat, in which we designed a type to contain history entries. We need not invent the operations to apply to the chessboard type; they are specified for us already, namely reading and printing a board and checking it for safe queen placement.

What else is required for a solution?

We will also need to write a driver program to test our code. This should be straight forward, since together the three functions fit nicely into an input-process-output test loop:

while True:
ReadBoard(board)
PrintBoard(board)
if Safe(board):
print('Board is safe.')
else:
print('Two queens attack.')

Stop & Predict

Should the program figure out which queens threaten each other?

Note that the Safe function needs only to check if any queens threaten one another; it is not required to report which queens are doing the threatening.

What kind of data structure should be used, and how large should it be?

The representation of the board will probably involve some sort of array, since an array provides a good way to store a collection of similar objects (board squares or queens). To use an array, we must know how big to declare it. The problem statement does not say how many queens there will be. Presumably there will be more than one. There can be at most 64, the number of squares on the chessboard.

The chessboard resembles a two-dimensional array, so an 8-by-8 array is a possible choice for the BoardType data type. Each square of the chessboard would be one cell of the array. Since we need to store only whether or not each square contains a queen, the array elements could be of type boolean, and BoardType would be defined as follows:

BoardType = [[False]*8 for _ in range(8)]

Stop & Predict

Why not use an array of one-dimensional arrays?

We might also use an array of one-dimensional arrays, which would look like this:

RowType = [False for x in range(8)]
DifferentBoardType = [RowType for x in range(8)]

Which definition is better?

The two definitions are essentially equivalent in Python, so the way to choose between them is to see which one best communicates the use of the type. The definition of RowType says that a "row" is a meaningful object. The definition of Different BoardType says that a "board" is a collection of rows. These definitions would be appropriate if access to an individual cell always required selecting its row first. On a chessboard, however, rows aren't any more meaningful than columns. This symmetry is reflected in the original BoardType declaration.

Stop & Help

Write code that places a queen at a position identified by values in variables rowLocation and columnLocation for each choice for BoardType (a two-dimensional array and an array of arrays).

Stop & Predict

What other representations might be used for the chessboard?

Thus we choose to represent BoardType as an 8-by-8 array of booleans, where each cell containing true represents a square occupied by a queen and each cell containing false represents an empty square. We move on to design the three functions ReadBoard, Safe, and PrintBoard.

Stop & Predict

Which of the three functions is likely to be easiest to design, and which will be the most difficult?

How is PrintBoard coded?

PrintBoard will be the easiest of the three functions to design. Printing a chessboard will be done line by line, as in the Banners With CLASS and the Calendar Shop programs:

for lineNum in range(8):
print the lineNumth line of the chessboard

Each line of the output corresponds to a row of the board array. Even though we didn't define the row as a separate array type, we may still apply the "process every element of an array" template to print the row:

for column in range(8):
if board[lineNum, column]:
print('Q', end = '')
else:
print('.', end = '')
print("\n")

In what ways might board values be read from the user?

There are several ways to ask the user for input. We could ask the user about each square on the board, in an interaction like the following:

Is there a queen in square [1,1]? no
Is there a queen in square [1,2]? yes
Is there a queen in square [1,3]? no

We could have the user type a diagram of the chessboard, eight lines of eight characters each, with one character representing a square containing a queen and another character representing a blank square. The input might then be as follows:

. . . . . . . .
. . . . . Q. .
. . . . . . . .
. . . . . . . .
. . . Q. . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Probably the easiest way for the user to type the data, however, is to provide just the row and column positions for each queen. A dialog to ask the user for the queen placement shown above might appear as follows:

Please type the row and column position for each queen.
Type 9 9 when done.
Queen row and column? 1 5
Queen row and column? 4 3
Queen row and column? 9 9

How will the input function work?

The Readboard function uses familiar templates to prompt the user for rows and columns. In each iteration, it reads a row and column and, if they are legal, sets the corresponding board entry to true. Here's the code:

for row in range(8):
for column in range(8):
board[row][column] = False
print('Please type the row and column position for each queen.')
print('Type 9 9 when done.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)
while (row != 9) or (column != 9):
if (row in range(8)) and (column in range(8)):
board[row][column] = True
else:
print('Please type values between 1 and 8.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)

Stop & Help

What templates are implemented in the ReadBoard function?

What decompositions for the Safe function make sense?

Only the Safe function remains to be written. The Problem Background suggests two decompositions. It says: "Two queens are said to attack each other if either can move to the position of the other if they are in the same row, column, or diagonal."

One approach is organized around queens; it will successively find each queen and see if it can move to the position of any other queen. We'll call this the queen-by-queen solution. Another approach checks whether any row, column, or diagonal, contains more than one queen. We'll call this the line-by-line solution.

What is the pseudocode for the queen-by-queen approach?

Translated into pseudocode, the queen-by-queen decomposition is

for each queen, do the following:
check squares on the queen's row;
if any contain another queen, return false;
check squares on the queen's column;
if any contain another queen, return false;
check squares on the queen's diagonols;
if any contain another queen, return false;
if no queen attacks another, return true;

Stop & Help

Why is this a better approach than comparing queens two at a time?

What is the pseudocode for the line-by-line approach?

Pseudocode for the line-by-line solution is as follows:

for each row, do the following:
if the row contains more than one queen, return false;
for each column, do the following:
if the column contains more than one queen, return false;
for each diagonal, do the following:
if the diagonal contains more than one queen, return false;
if no row, column, or diagonal has more than one queen, return true;

We will consider each decomposition in turn.

Analysis

9.4 Under what conditions might each of three ways described for reading a board from the user be appropriate?

Modification

9.5 Modify ReadBoard to ask the user about each square on the chessboard.

Modification

9.6 Modify ReadBoard to read a board configuration represented by eight lines of Q's and periods.

Modification

9.7 Give Python type definitions that define BoardType as an 8-by-8 array of characters, with 'Q' representing a square with a queen and a blank representing an empty square.

Modification

9.8 Give Python type definitions for a chessboard, each square of which may contain a queen, a king, a rook, a bishop, a knight, or a pawn.

Application

9.9 Which of the following would probably be the better way to represent the seats in an auditorium?

RowType = [False for _ in range(NUMSEATS)]
AuditoriumType = [RowType for _ in range(NUMROWS)]

or

AuditoriumType = [[False]*NUMSEATS for _ in range(NUMROWS)]

Briefly explain, by describing ways in which the auditorium data type might be used.

The Queen-by-Queen Solution

What are the main steps in the queen-by-queen solution?

The queen-by-queen solution involves searching the array board for queens and checking each queen to see if it attacks any other queen.

Stop & Predict

Does the program have to check every queen?

How are queens located?

Queens are located by searching the array using the two-dimensional version of "process every element of an array":

for row in range(8):
for column in range(8):
process board[row][column]

What should happen when a queen is located?

We can replace the "process" line in this template with code that checks if the cell contains a queen, then deals with the queen. We rename the row and column variables to be queenRow and queenCol to arrive at the following:

def Safe(board):
attacking = False
queenRow = 0
queenCol = 0
for queenRow in range(8):
for queenCol in range(8):
if board[queenRow][queenCol]:
check the squares in the queenRow-th row
if any contain another queen,
set attacking to true
check the squares in the queenCol-th column
if any contain another queen,
set attacking to true
check the squares appropriate diagonals
if any contain another queen,
set attacking to true
Safe = not attacking
return Safe

Stop & Help

Why is Safe assigned the value not attacking at the end of the function?

Stop & Predict

How many attacks will this code locate?

How can attacking queens be found more efficiently?

This solution continues to search after two attacking queens have been located, since the for loops always check every row and column. A more efficient approach uses while loops with a boolean variable to indicate when an attacking queen is located. The pseudocode is as follows:

def Safe(board):
attacking = False
queenRow = 0
queenCol = 0
while not attacking and (queenRow <= 7):
queenCol = 0
while not attacking and (queenCol <= 7):
if board[queenRow][queenCol]:
check the squares in the queenRow-th row
if any contain another queen,
set attacking to true
check the squares in the queenCol-th column
if any contain another queen,
set attacking to true
check the squares appropriate diagonals
if any contain another queen,
set attacking to true
queenCol = queenCol + 1
queenRow = queenRow + 1
Safe = not attacking
return Safe

Stop & Help

Which one-dimensional array template is extended to two-dimensional arrays in this pseudocode?

How should the squares a queen can attack be checked?

To check for other queens in a given queen's row, column, and diagonals, one can either start at the queen's position and work forward and backward or start at the beginning of the row or column or diagonal and examine the whole thing, being careful to ignore the queen. The two ways are diagrammed below. We start with the first way. The second way resembles the line-by-line decomposition we plan to try next.

Stop & Predict

Which of the two waysfor checking the squares a queen can move to will be easier to code?

How are diagonals checked?

The diagonals are clearly the most difficult part of the program. To search a diagonal of the chessboard, we need a loop with two loop variables, the row index and the column index, that get updated in parallel. For example, to examine the ways the queen above can move "southeast," the array elements board [5,4], board [6,5], board [7,6], and board [8,7] must be checked.

Stop & Consider

Why not use two loops, one nested within the other?

Stop & Help

Show how the row and column indexes change along "southeast" diagonals and "southwest" diagonals.

Which is better, a for loop or a while loop?

Either a for loop or a while loop could be used to check the diagonals, since the number of squares to check can be computed from the queen's position. A for loop could be controlled by a variable that takes on values of (say) the row index, and whose body contains an update to a variable that takes on values of the column index. The for loop approach would highlight one of the index variables by selecting it as the loop variable.

However, since both the row and the column index variables are equally important and used in pretty much the same way, the highlighting of one of the variables obscures the purpose of the code. We prefer to use a while loop to show the equal importance of the row and column variables more clearly. In addition, the use of while makes clear (in the same way as in the Safe function) that it is not necessary to check the rest of the diagonal once a queen is located.

Stop & Predict

When should the program stop checking in the southeast direction? In the southwest direction?

The code below checks the queen's southeast moves.

row = queenRow + 1
col = queenCol + 1
while not attacking and (row <= 7) and (col <= 7):
if board[row][col]:
attacking = True
else:
row = row + 1
col = col + 1

Stop & Help

Write code to check the queen's southwest moves.

Stop & Predict

Are four diagonal-checkin functions needed?

How can a single function be used to check all four diagonals?

Four functions to do essentially the same thing seem like too much. Instead, we convert the separate functions into a single function that takes the direction of search and the location of the queen as parameters.

Stop & Predict

Write the general function for checking all four diagonals before looking at the code in the Python Code section.

How can rows and columns be checked?

We code the row and column searches as while loops, to be consistent with the diagonal searches. This results in the function listed in the Python Code section.

How can the code be tested?

Before testing this code, we note that the queen-by-queen solution looks for pairs of queens. Thus, simple tests of the program's correctness require boards that contain only two queens. Simple test data make it easier to zero in on bugs if they do turn up. Testing the queen-by-queen solution involves anticipating all the usual problems with arrays.

Stop & Help

What cases test for the common array bugs?

What boundary cases should be tested?

For our purposes, boundary cases are the first row and column and the eighth row and column. Other boundary cases involve the relative positions of the queens; we should test situations where the queens are adjacent, as well as situations where the queens are as far apart as possible.

What other cases are important?

Every possibility for queen placement should be tested. We should include boards in which two queens can attack each other as well as boards in which there are no attacking queens. It happens that we can test all the ways for two queens to attack each other:

• two queens in the same row
• two queens in the same column
• two queens in the same northeast/southwest diagonal
• two queens in the same northwest/southeast diagonal

Stop & Help

Devise a comprehensive set of test cases and test the program just designed.

Analysis

9.10 What are the differences between the row searches and the diagonal searches? What are the similarities?

Analysis

9.11 Suppose that the board contains queens at positions [3,6] and [5,4]. How many board squares are examined by the just-designed Safe function to determine whether or not the two queens attack each other? (A board square at position [row, col] is "examined" when board[row, col] is evaluated.) If a board square is examined more than once, include it once in the count for each examination.

Analysis

9.12 How many board squares are examined in the Safe function for a board containing queens at positions [3,3] and [7,6]?

Modification

9.13 Modify the Safe function to count the number of board squares it examines and print the result before it returns.

Modification

9.14 Code the row and column searches as a single function that takes the row and column location of the queen and an indicator of what is being searched as parameters.

Modification

9.15 Write a single search function that has two integer parameters in place of the direction parameter. Both of the integers will have value 0, -1, or +1. One will be the amount to increment the row variable each time through the search loop; the other will be the amount to increment the col variable each time through the loop. Recode Safe to call the new function for row, column, and diagonal search.

Modification, Reflection

9.16 Recode the while loops in the Safe function to use a while not done, as in earlier case studies, instead of the and expression. Which version do you think is better and why?

Debugging

9.17 Consider the following code to check if other queens are on the same row as the queen at position [queenRow, queenCol].

for k in range(8):
if board[queenRow][queenCol]:
attacking = True

What is wrong with the code?

Testing

9.18 For what test cases will the above code correctly set attacking to true?

The Line-by-Line Solution

How is this solution different from the queen-by-queen solution?

The line-by-line solution checks each row, column, or diagonal to see if it contains more than one queen. The main difference is that the program keeps track of how many queens appear instead of just searching for a single queen.

Stop & Predict

Which one-dimensional array template can be applied to searching rows in a two dimensional array?

How are the rows searched for queens?

Searching rows for multiple queens involves counting the number of true entries in a row and then setting the boolean variable of attacking to true if we find a row that contains more than one queen. The code looks like this:

numQueens = 0
col = 0
while not attacking and (col <= 7):
if board[row][col]:
numQueens = numQueens + 1
else:
col = col + 1
attacking = (numQueens > 1)

Stop & Help

Why is attacking set to (numQueens > 1)?

We code this as a function RowAttack, which returns a boolean value saying whether two queens attack each other along some row. A boolean function is better than a function since we need to know only any two queens attack, not how many attacking queens are in the row.

Stop & Help

Create a boolean function called ColumnAttack.

Stop & Help

Express the row and column checks as calls to a single function.

How should the diagonals be checked?

Just as checking the diagonals was the hardest part of the queen-by-queen approach, it is the most difficult part of the line-by-line approach. Since the checking can start at the beginning of each diagonal rather than somewhere in the middle, we need consider only two directions (say, northeast and southeast). Figure 9.1 illustrates the process.

What is the pattern for searching diagonals?

Figure 9.1 suggests a natural subdivision for the diagonals as follows:

• Search the southeast diagonals that start in the first column.
• Search the southeast diagonals that start in the first row.
• Search the northeast diagonals that start in the first column.
• Search the northeast diagonals that start in the eighth row.

The southeast diagonals that start in the first column are those starting in row 1, row 2, up to row 7. They can be searched with the following loop:

row = 0
while not attacking and (row <= 6):
search the southeast diagonal starting at [row, 0]
row = row + 1

Similarly, searching the southeast diagonals that start in the first row can be done as follows:

col = 0
while not attacking and (col <= 6):
search the southeast diagonal starting at [0, col]
col = col + 1

Stop & Help

Write pseudocode for searching the northeast diagonals.

Stop & Predict

How are these searches similar?

How can these search routines be coded as a single subprogram?

The pseudocode for all the diagonal searches is quite similar. In fact, it is similar to the code for the searches of the rows and columns.

We compare the code for searching a row with the code for searching the southeast diagonals:

# Search a row
numQueens = 0
col = 0
attacking = False
while not attacking and (col <= 7):
if board[row][col]:
numQueens = numQueens + 1
col = col + 1
attacking = (numQueens > 1)

# Search a southeast diagonal
numQueens = 0
row = 0
attacking = False
while not attacking and (row <= 6):
if board[row][col]:
numQueens = numQueens + 1
row = row-1
col = col+1
attacking = (numQueens > 1)

Stop & Help

How are these routines similar, and where are they different?

There are four places where these routines vary: the initial row and column at which the search is to start and the amounts that row and col are incremented each time through the loop. Using these four values along with the board itself as parameters, we can write a single function that does all the searching:

def LineAttack(board, rowStart, colStart, rowChange, colChange):
row = 0
col = 0
numQueens = 0
attacking = False
row = rowStart
col = colStart
while not attacking and (row
in range(8)) and (col in range(8)):
if board[row][col]:
numQueens = numQueens + 1
row = row + rowChange
col = col + colChange
attacking = (numQueens > 1)
LineAttack = attacking

How would LineAttack be called to search a row?

A row search could be done by the following code:

if LineAttack(board, row, 1, 1, 0):

Stop & Help

Call LineAttack to search a given column and to search all the diagonals.

Putting it all together, we get the function in the Python Code section.

Stop & Help

Create test cases and test the program just designed.

Testing

9.19 What special test cases are needed for the line-by-line version that are not needed for the queen-by-queen solution?

Analysis

9.20 Describe the template for searching a two-dimensional array, using a verbal description, pseudocode, code, and an illustration

Application

9.21 Create a program that takes as input the locations of queens and indicates on a chessboard the squares that are not threatened by any queen. The program should output rows of 8 characters where ones indicate threatened squares and zeroes indicate unthreatened squares.

Debugging

9.22 Consider the following version of RowAttack.

while not attacking and (col <= 7):
if board[row][col]:
numQueens = numQueens + 1
attacking = (numQueens > 1)
else:
col = col + 1

Analysis

There's a bug in the code. Find and fix it.

9.23 Describe all rows for which attacking has the correct value upon termination of the while loop in the version of RowAttack in question 9.22.

Reflection

9.24 Describe bugs that could arise when using two-dimensional arrays but that would probably not arise in applications using one-dimensional arrays.

Debugging

9.25 Suppose a version of LineAttack never detected queens in the same column. Is the bug in LineAttack or in the code that calls LineAttack? How would you find out for sure?

Analysis

9.26 How many board squares are examined in the line-by-line version of the Safe function for a board containing queens at positions [3,6] and [5,4]? If a board square is examined more than once, include it once in the count for each examination.

Analysis

9.27 How many board squares are examined in the line-by-line version of the Safe function for a board containing queens at positions [3,3] and [7,6]?

Modification

9.28 Modify the line-by-line version of the Safe function to count the number of board squares it examines and print the result before it returns.

The Queen Position Representation

What aspects of the solution could be improved?

We considered the two-dimensional array representation of the chessboard because the board resembles a two-dimensional array in form. A problem with this representation, however, is that the Safe function wastes a lot of time examining squares that do not contain a queen.

More generally, the boardType data type represents a set of queen positions, each indicated by a row index and a column index. Typically there are (at least) two ways to represent a set of elements. One is as a boolean array, with cells for all possible elements in the set. The two-dimensional boolean chessboard was an example. A second way to represent a set is to store its elements in a one-dimensional array. To represent a chessboard,the array would contain the queen positions: the first element would contain the position of the first queen, the second element would contain the position of the second queen, and so on.

Stop & Predict

Given the row and column positions of two queens, determine if they attack each other.

How could the row and column indices be represented?

Each queen position has two components, a row index and a column index. This suggests the use of a dictionary to store an individual queen position. We then represent the board as an array of 64 queen positions, along with the number of queens on the board, packaged in a dictionary as follows:

QueenPosType = {
"row": 0,
"col": 0
}
queens = []
for i in range(64):
queens.append( QueenPosType.copy())
BoardType = {
"queens1": queens.copy(),
"numQueens": integer
}

The figure below displays this representation.

How do the row and column indices of two queens determine if the queens attack?

A solution using this representation would take advantage of the numerical relationships between the position indices of queens that attack each other. Certainly two queens attack if their row values are identical, or their column values are identical. Again we have a problem with the diagonals.

How can the diagonals be checked?

To find a computational way to check the diagonals we use the usual function of looking for a pattern in the diagonal locations.

Stop & Predict

What aspects of diagonals make it likely that a pattern exists?

We inspect two sample diagonals, one southeast, the other northeast. These are pictured below.

What is the pattern?

Consider moving along the northeast diagonal. Whenever the row index goes down, the column index goes up by the same amount. That is, the sum of the row and column indexes stays the same. Looking at the figure above, the row and column indexes of any position on the given northeast diagonal add to 7.

Stop & Predict

What happens on the southeast diagonal?

For the southeast diagonal, an increase in the row index corresponds to an increase in the column index, by the same amount. Therefore, the difference of the row and column indexes stays the same. On the southeast diagonal pictured above, the difference between the row and column indexes is always -1.

How can this information be used to detect an attack?

These observations provide a way to detect an attack along the diagonal. Suppose we have two queens, one at position [row1, column1], the other at position [row2, colunnn2]. If the sum of row1 and column1 is the same as the sum of row2 and column2, the two queens are on the same northeast diagonal. If the difference of row1 and column is the same as the sum of row2 and column2, the two queens are on the same southeast diagonal.

Stop & Help

Write the code to compare the diagonal values of the two queens described above.

What shortcuts can be used?

It seems clear that if more than eight queens are input at least two will be in the same row or column. Thus Safe can begin by checking if the number of queens is 8 or more, and return true if so.

How will the code work?

Given an array of queens each represented as a QueenPosType, we compare each pair of queens to see if they are on the same row, column, or diagonal. Pairs of elements in an array are processed by applying a variation of the template "process every element of an array"; the "processing" here is to consider all pairs that involve the given element. In order not to consider a given pair of queens twice, we pair each queen with all the queens that follow it in the array. To do that, however, we merely apply the template again to the subarray of queens that follow the given element. The figure below illustrates this process.

Here is the code.

j = 1
done = False
while (j <= number of elements) and not done:
k = j+1
while (k<=number of elements) and not done:
see if the j-th and k-th elements
of the array satisfies the condition,
and if so, set done to true
k = k + 1
j = j + 1

What does the code look like?

We apply this template, providing a better name for "done," and substituting the code for the attack condition:

(queens[j]["row"] == queens[k]["row"])
or (queens[j]["col"] == queens[k]["col"])
or (queens[j]["row"] + queens[j]["col"] == queens[k]["row"] + queens[k]["col"])
or (queens[j]["row"] - queens[j]["col"] == queens[k]["row"] - queens[k]["col"])

This test is messy enough to warrant putting it into a function to hide its details. We'll call it Attack.

How is ReadBoard coded for this representation?

The ReadBoard function for this version is even easier to write than the ReadBoard function for the first representation, since the way we are storing the board corresponds exactly to the way we are requesting queen positions from the user. The code mainly consists of a loop around two statements, one that reads values for row and column, the other that sets the corresponding board entry to true.

How is PrintBoard coded for this representation?

PrintBoard, on the other hand, requires same thought. The line-by-line loop will still be appropriate, as will the column-by-column loop within it. Printing the character for each board position, however, requires determining whether or not a queen appears at that position.

Stop & Predict

How should the character to print at a given row and column position be determined?

One way to find out if a queen is at a given position is to search for the rowcolumn pair in the board array. This approach merely requires that we copy a search function from earlier programs.

Another way is to set up a "board image" array similar to the board representation used in the earlier versions of this program. The board image will be an 8-by-8 array of characters, each either '.'or 'Q'; once constructed, it can be printed using the "process every element of a two-dimensional array" template.

Constructing the array is straightforward. First comes an initialization step, in which all the array elements are set to '.'. Then we process every element of the board array, setting the corresponding board image element to 'Q'.

The Python Code section contains the complete set of revised functions and type definitions.

Stop & Help

Devise test data and check this version of the program. How is a comprehensive set of test data for this version different from test boards used for the other two versions?

Analysis

9.29 Does the order in which the queens are stored in the array affect the number of board squares examined in the Safe function? Why or why not?

Analysis

9.30 Does the order in which the queens are stored in the array affect the number of board squares examined in the PrintBoard function? Why or why not?

Analysis

9.31 How many board squares are examined in the version of the Safe function just designed for a board containing seven queens?

Analysis

9.32 How many board squares are examined in the version of the Safe function just designed for a board containing N queens?

Modification

9.33 Rewrite the PrintBoard function so that, instead of using a board image array, it searches the board array inside the printing loop to determine whether to print a '.' or a 'Q'. Which version do you prefer, and why?

Outline of Design and Development Questions

These questions summarize the main points of the commentary.

Understanding the Problem and Selecting an Implementation
How does this problem resemble problems in earlier case studies?
What else is required for a solution?
What kind of data structure should be used, and how large should it be?
Which definition is better?
How is PrintBoard coded?
In what ways might board values be read from the user?
How will the input function work?
What decompositions for the Safe function make sense?
What is the pseudocode for the queen-by-queen approach?
What is the pseudocode for the line-by-line approach?

The Queen-by-Queen Solution
What are the main steps in the queen-by-queen solution?
How are queens located?
What should happen when a queen is located?
How can attacking queens be found more efficiently?
How should the squares a queen can attack be checked?
How are diagonals checked?
Which is better, a for loop or a while loop?
How can a single function be used to check all four diagonals?
How can rows and columns be checked?
How can the code be tested?
What boundary cases should be tested?
What other cases are important?

The Line-by-Line Solution
How is this solution different from the queen-by-queen solution?

How are the rows searched for queens?
How should the diagonals be checked?
What is the pattern for searching diagonals?
How can these search routines be coded as a single subprogram?
How would LineAttack be called to search a row?

The Queen Position Representation
What aspects of the solution could be improved?
How could the row and column indices be represented?
How do the row and column indices of two queens determine if the queens attack?
How can the diagonals be checked?
What is the pattern?
How can this information be used to detect an attack?
What shortcuts can be used?
How will the code work?
What does the code look like?
How is ReadBoard coded for this representation?
How is PrintBoard coded for this representation?

Programmers' Summary

The problem in this case study is to design a data type to represent a chessboard containing queens and to implement three operations on the board: reading it, printing it, and checking if any of the queens are mutually attacking. The commentary contrasts two ways to represent of elements in this case, sets of queens.

One approach is to indicate members of a set of elements with a boolean array, in which each possible element is represented by a position in the array. A value of true in an array cell means that the corresponding element is in the set, and a value of false means that the element is not in the set.A set of single-digit integers, for example, would be represented as a ten element boolean array, and the set {3, 1, 4, 9} would be stored as follows:

Two of the solutions use an 8-by-8 boolean array of queen positions to represent the set of queens. The Python set data type is also stored internally in this way.

Another way to represent a set of elements is to store them in an array. The array would still be declared to have ten cells to allow for the largest possible set, but for smaller sets some of the array cells would be unused. Thus the set {3, 1, 4, 9} might be stored as

or, to make certain set operations more efficient, as

where the set elements are stored in order. Another of our solutions uses this approach.

Code that uses the two-dimensional array representation of the board is designed using two-dimensional versions of templates previously used for one-dimensional arrays. Generally, two applications of the "process every array element" or "search an array" are involved, one to process or search the "array" of rows, the other to process or search the elements in the given row. Searching the board's diagonals is not so straightforward; it invalues a single loop in which two index variables are updated in parallel.

Two solutions are described for the Safe function, which checks for attacking queens. One, the queen-by-queen solution, is organized around the queens on the board; it locates a queen and checks all the rows, columns, and diagonals that the queen threatens for other queens. Another, the line-by-line solution, searches each row, column, and diagonal for multiple queens. The line-by-line solution is less complicated, since entire "lines" (rows, columns, or diagonals) of a two-dimensional array can be processed more easily than partial lines. Straightforward coding produces separate search functions for the rows, the columns, and the diagonals. Further inspection, however, reveals that all these functions are performing essentially the same action; by adding two parameters that indicate the sequence in which board elements are to be examined, we can combine them all into one function.

The alternative board representation, the array of queen positions, leads to the simplest, shortest, and most efficient code for Safe. It avoids needlessly checking blank squares. It requires a bit of cleverness to devise, however, namely noticing the pattern of row and column indexes for each diagonal. Comparison of pairs of queens is done by applying the "process every element of an array" twice, once to select an element, the other to pair it with queens occurring subsequently in the array. Printing the board reuses the approach from the earlier versions by building and printing a two-dimensional board image array of characters.

Making Sense of Chess Challenges

Analysis

9.34 Compare the three solutions. The queen position solution is more efficient; why would efficiency matter? Which is more understandable? Which is easier to test and debug?

Modification

9.35 Write a routine that takes input from the 8-by-8 boolean array and converts it to the data structure used in the queen position solution.

Analysis

9.36 Use algebra to compute the formulas for the diagonals and to show why the queen position solution works. Hint: The slopes of the diagonals are +1 and -1.

Application

9.37 Design a representation for a chessboard to be used in a program to play chess. It will contain pieces for two players. The queen is one of the pieces; others are the king, the rook, the bishop, the knight,and the pawn.

Modification

9.38 Modify each version of the code to use the data type designed in question 9.37. Check the board for pieces of one player that can attack pieces of the other. Here are some rules about chess pieces: A king attacks any piece in an adjacent square. A rook attacks a piece in the same row or column. A bishop attacks a piece on the same diagonal. A knight attacks a piece two squares in one row or column and one square in the perpendicular row or column. A pawn attacks a piece that's one square diagonally ahead of it.

Modification

9.39 Rewrite each version of the Safe function to return the positions of one of the pairs of attacking queens.

Analysis

9.40 What changes to the queen position solution would be necessary to stop checking as soon as two attacking queens were detected?

Analysis

9.41 Does an error occur in any of the programs if only one queen position is read in ReadBoard? Explain why or why not.

Reflection

9.42 Name the difficulties in extending templates for one-dimensional arrays to two-dimensional arrays.

Reflection

9.43 What did you learn from the queen-by-queen solution that made it easier to understand the queen position solution?

Application

9.44 The game of 5-in-a-row Tic-Tac-Toe is played by two players on a 19-by-19 board. The players take turns marking empty board squares, one player with an X, the other with an O. The first player to get five of his or her marks in a row, column, or diagonal wins. In a program to play 5-in-a-row Tic-Tac-Toe, is it better to store the board as a two-dimensional array of characters or as an array of positions of X's and O's? Explain.

Linking to Previous Case Studies

Analysis

9.45 Compare the use of for loops and while loops to search an array in Space Text, You Are What You Eat, You Forgot What You Ate, and Chess Challenges. When is it important to cut short the search by using a while loop, and what disadvantages arise as a result?

Modification

9.46 Modify the Banners With CLASS program to store letter patterns in a two-dimensional array. One advantage of doing this is that letters can be printed across the line as well as down the screen. What is a disadvantage?

Modification

9.47 Modify The Calendar Shop program to use a two-dimensional array to store the days of the month, then print it all at once.

Application

9.48 Why might one wish to store a calendar in a two-dimensional array?

Reflection

9.49 Compare the process used to print the fat and calorie graphs in You Are What You Eat with the process used to print the chess board in the queen position solution. What techniques are used in both?

Modification

9.50 Rewrite the graph-printing functions in You Are What You Eat to construct and print a two-dimensional "graph-image" array.

Reflection

9.51 Space Text, You Are What You Eat, You Forgot What You Ate, and Chess Challenges all involve designing and implementing abstract operations for a given collection of information. What are the similarities and differences between the sets of operations designed in these case studies? What operations are likely to be needed for any abstract data type?

PYTHON CODE

Queen-by-Queen Checking

NW = 1
NE = 2
SE = 3
SW = 4
DEBUGGING = True
BoardType = [[False]*8 for _ in range(8)]
DirectionType = 0
StringType = ''
board = BoardType.copy()

# Read values for the board, coordinates for queen positions.

def ReadBoard(board):
row = 0
column = 0
for row in range(8):
for column in range(8):
board[row][column] = False
print('\nPlease type the row and
column position for each queen.')
print('Type 9 9 when done.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)
while (row != 9) or (column != 9):
if (row in range(8)) and (column in range(8)):
board[row][column] = True
else:
print('Please type values between 1 and 8.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)

""" Print the board, indicating a square that contains a queen by 'Q' and an empty square by '.'. """

def PrintBoard(board):
lineNum = 0
column = 0
for lineNum in range(8):
for column in range(8):
if board[lineNum][column]:
print('Q ', end = '')
else:
print('. ', end = '')
print("")

def DebugPrint(msg, queenRow, queenCol):
if DEBUGGING:
print(msg, queenRow, queenCol)

""" Return true exactly when board contains another queen in the same row as [gueenRow, queenCol]. """

def SafeRow(board, queenRow, queenCol):
row = 0
col = 0
attacking = False
col = queenCol - 1
while (col >= 1) and not attacking:
if board[queenRow][col]:
attacking = True
else:
col = col - 1
col = queenCol + 1
while (col <= 7) and not attacking:
if board[queenRow][col]:
attacking = True
else:
col = col + 1
SafeRow = attacking
return SafeRow

""" Return true exactly when board contains another queen in the same column as [queenRow, queenCol]. """

def SafeCol(board, queenRow, queenCol):
row = 0
col = 0
attacking = False
row = queenRow - 1
while (row >= 1) and not attacking:
if board[row][queenCol]:
attacking = True
else:
row = row - 1
row = queenRow + 1
while (row <= 7) and not attacking:
if board[row][queenCol]:
attacking = True
else:
row = row + 1
SafeCol = attacking
return SafeCol

""" Return true exactly when board contains another queen somewhere in the given direction from [queenRow, queenCol]. The direction will either be northwest (NW), northeast (NE), southwest (SW), or southeast (SE) """

def SafeDiag(board, queenRow, queenCol, direction):
row = 0
col = 0
attacking = False
if direction == NE:
row = queenRow - 1
if direction == NW:
row = queenRow - 1
if direction == SE:
row = queenRow + 1
if direction == SW:
row = queenRow + 1
if direction == NW:
col = queenCol - 1
if direction == SW:
col = queenCol - 1
if direction == NE:
col = queenCol + 1
if direction == SE:
col = queenCol + 1

while not attacking and (row >= 0) and
(row <= 7) and (col >= 0) and (col <= 7):
if board[row][col]:
attacking =True
else:
if direction == NE:
row = row - 1
if direction == NW:
row = row - 1
if direction == SE:
row = row + 1
if direction == SW:
row = row + 1
if direction == NW:
col = col - 1
if direction == SW:
col = col - 1
if direction == NE:
col = col + 1
if direction == SE:
col = col + 1
SafeDiag = attacking
return SafeDiag

""" Return true exactly when board contains two mutually attacking queens """

def Safe(board):
qRow = 0
qCol = 0
attacking = False
while not attacking and (qRow <= 7):
qCol = 0
while not attacking and (qCol <= 7):
if board[qRow][qCol]:
if SafeRow(board, qRow, qCol):
attacking = True
DebugPrint ('queen on same row
as ', qRow, qCol)
elif SafeCol(board, qRow, qCol):
attacking = True
DebugPrint ('queen on same column
as ', qRow, qCol)
elif SafeDiag(board, qRow, qCol, NW):
attacking = True
DebugPrint ('queen on same NW
diagonal as ', qRow, qCol)
elif SafeDiag(board, qRow, qCol, NE):
attacking = True
DebugPrint ('queen on same NE
diagonal as ', qRow, qCol)
elif SafeDiag(board, qRow, qCol, SE):
attacking = True
DebugPrint ('queen on same SE
diagonal as ', qRow, qCol)
elif SafeDiag(board, qRow, qCol, SW):
attacking = True
DebugPrint ('queen on same SW
diagonal as ', qRow, qCol)
qCol = qCol + 1
qRow = qRow + 1
Safe = not attacking
return Safe

# Main Program

while True:
ReadBoard(board)
PrintBoard(board)
if Safe(board):
print('Board is safe.')
else:
print('Two queens attack.')

Line-by-Line Checking

NW = 1
NE = 2
SE = 3
SW = 4
DEBUGGING = True
BoardType = [[False]*8 for _ in range(8)]
DirectionType = 0
StringType = ''
board = BoardType.copy()

# Read values for the board, coordinates for queen positions.

def ReadBoard(board):
row = 0
column = 0
for row in range(8):
for column in range(8):
board[row][column] = False
print('\nPlease type the row and
column position for each queen.')
print('Type 9 9 when done.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)
while (row != 9) or (column != 9):
if (row in range(8)) and (column in range(8)):
board[row][column] = True
else:
print('Please type values between 1 and 8.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)

""" Print the board, indicating a square that contains a queen by 'Q' and an empty square by '.'. """

def PrintBoard(board):
lineNum = 0
column = 0
for lineNum in range(8):
for column in range(8):
if board[lineNum][column]:
print('Q ', end = '')
else:
print('. ', end = '')
print("")

def DebugPrint(msg, n):
if DEBUGGING:
print(msg, n)

""" Return true exactly when, starting at position [rowStart, colStart] and moving in the direction specified by rowChange and colChange, two or more queens are encountered on the board. """

def LineAttack(board, rowStart, colStart, rowChange, colChange):
numQueens = 0
row = rowStart
col = colStart
attacking = False
while not attacking and (row
in range(8)) and (col in range(8)):
if board[row][col]:
numQueens = numQueens + 1
row = row + rowChange
col = col + colChange
attacking = (numQueens > 1)
LineAttack = attacking
return LineAttack

""" Return true exactly when board contains no mutually attacking queens """

def Safe(board):
row = 0
col = 0
attacking = False
while not attacking and (row <= 7):
if LineAttack(board, row, 0, 0, +1):
attacking = True
DebugPrint ('multiple queens
found in row ', row)
elif LineAttack(board, row, 0, +1, +1):
attacking = True
DebugPrint ('multiple queens found
going SE from row ', row)
elif LineAttack(board, row, 0, -1, +1):
attacking = True
DebugPrint ('multiple queens found
going NE from row ', row)
else:
row = row + 1
while not attacking and (col <= 7):
if LineAttack(board, 0, col, +1, 0):
attacking = True
DebugPrint ('multiple queens
found in column ', col)
elif LineAttack(board, 0, col, +1, +1):
attacking = True
DebugPrint ('multiple queens
going SE from column ', col)
elif LineAttack(board, 0, col, -1, +1):
attacking = True
DebugPrint ('multiple queens
going SW from column ', col)
else:
col = col + 1
Safe = not attacking
return Safe

# Main Program

while True:
ReadBoard(board)
PrintBoard(board)
if Safe(board):
print('Board is safe.')
else:
print('Two queens attack.')

Queen Position Representation

QueenPosType = {
"row": 0,
"col": 0
}
DEBUGGING = True
queens1 = []
for i in range(64):
queens1.append( QueenPosType.copy())
BoardType = {
"queens": queens1.copy(),
"numQueens": 0
}
StringType = ''
board = BoardType.copy()

""" Fill the board array with positions entered by the user """

def ReadBoard(board):
queenPos = QueenPosType
board["numQueens"] = 0
print('Please type the row and
column position for each queen.')
print('Type 9 9 when done.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)
queenPos["row"] = row
queenPos["col"] = column
while (queenPos["row"] != 9) or
(queenPos["col"] != 9):
if (queenPos["row"] in range(8))
and (queenPos["col"] in range(8)):
board["queens"] [board
["numQueens"]] = queenPos.copy()
board ["numQueens"] = board ["numQueens"] + 1
else:
print('Please type values between 1 and 8.')
print('Queen row and column? ', end = '')
row, column = input().split()
row = int(row)
column = int(column)
queenPos["row"] = row
queenPos["col"] = column

# Print the board.

def PrintBoard(board):
lineNum = 0
column = 0
k = 0
boardDisplay = [['']*8 for _ in range(8)]
for lineNum in range(8):
for column in range(8):
boardDisplay [lineNum] [column] = '. '
for k in range( board["numQueens"]):
boardDisplay [board ["queens"] [k] ["row"]]
[board["queens"][k]["col"]] = 'Q '
for lineNum in range(8):
for column in range(8):
print( boardDisplay [lineNum]
[column], end = '')
print('')

def DebugPrint(q1, q2):
if DEBUGGING:
print('queens at positions {} {}
and {} {} attack.'.format(q1["row"],
q1["col"], q2["row"], q2["col"]))

""" Return true exactly when q1 and q2 represent positions on the same row column, or diagonal of the chessboard. """

def Attack(q1, q2):
Attack = (q1["row"] == q2["row"])
or (q1["col"] == q2["col"]) or
(q1["row"] + q1["col"] == q2["row"]
+ q2["col"]) or (q1["row"] -
q1["col"] == q2["row"] - q2["col"])
return Attack

""" Return true exactly when board contains no mutually attacking queens """

def Safe(board):
j = 0
k = 0
attacking = False
while (j < board ["numQueens"])
and not attacking:
k = j + 1
while (k < board ["numQueens"])
and not attacking:
attacking = Attack (board ["queens"]
[j], board["queens"][k])
if attacking:
DebugPrint( board ["queens"]
[j], board["queens"][k])
k = k + 1
j = j + 1
Safe = not attacking
return Safe

# Main Program

while True:
ReadBoard(board)
PrintBoard(board)
if Safe(board):
print('Board is safe.')
else:
print('Two queens attack.')